package algorithm.t202110;

import java.util.List;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/23 9:01
 * @description :9道
 * 羡慕南飞的雁。
 * persevere to last
 * 2021.10.23
 */
public class t20211023 {

    Integer[][] memory;

    //120.三角形最小路径和 解法二：递归 + 记忆化
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null) {
            return 0;
        } else if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }

        memory = new Integer[triangle.size()][triangle.size()];


        return dfs(triangle, 0, 0);

    }

    private int dfs(List<List<Integer>> triangle, int x, int y) {
        if (x == triangle.size()) {
            return 0;
        }

        if (memory[x][y] != null) {
            return memory[x][y];
        }

        memory[x][y] = Math.min(dfs(triangle, x + 1, y), dfs(triangle, x + 1, y + 1)) + triangle.get(x).get(y);
        return memory[x][y];

    }

    /*
        解法三：动态规划
        定义二维 dp 数组，将解法二中「自顶向下的递归」改为「自底向上的递推」。
        状态转移：dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
     */

    public int minimumTotal2(List<List<Integer>> triangle) {
        if (triangle == null) {
            return 0;
        } else if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }

        int size = triangle.size();
        int[][] dp = new int[size + 1][size + 1]; // dp[i][j] 表示从点 (i, j) 到底边的最小路径和。


        //从底至上来
        for (int i = size - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }

        }

        return dp[0][0];

    }


    /*
        有一分数序列：2/1,3/2,5/3,8/5,13/8,21/13...求出这个数列的前20项之和。
     */
    public double sum(int times) {
        double mu = 1, zi = 2;
        double sum = 0;

        for (int i = 0; i < times; i++) {
            sum += zi / mu;
            double temp = zi;
            zi = mu + zi;
            mu = temp;
        }

        return sum;
    }


    //492.构造矩形
    public int[] constructRectangle(int area) {
        int[] res = new int[2];
        if (area == 0) {
            return res;
        }

        for (int i = (int) Math.sqrt(area); ; i--) {
            if (area % i == 0) {
                return new int[]{area / i, i};
            }
        }

    }

    //231. 2的幂
    public boolean isPowerOfTwo(int n) {

        return n > 0 && (n & (n - 1)) == 0;


    }

    //191. 位1的个数
    public int hammingWeight(int n) {
        int count = 0;

        for (int i = 0; i < 32; i++) {
            count += n & 1;
            n = n >>> 1;
        }


        return count;
    }


    //面试题05.02 二进制数转字符串
    public String printBin(double num) {
        if (num >= 1 || num <= 0) {
            return new String("ERROR");
        }

        double s = 0.50;
        StringBuilder builder = new StringBuilder();
        builder.append("0.");

        while (num > 0) {
            if (builder.length() > 32) {//循环小数的情况
                return "ERROR";
            }

            if (num < s) {
                builder.append("0");
            } else {
                num = num - s;
                builder.append("1");
            }
            s = s / 2;
        }

        return builder.toString();

    }

    //面试题05.03 翻转数位
    public int reverseBits(int num) {
        int cur = 0;//当前1数量的最大值，遇到0置0，遇到1加1
        int insert = 0;//当前1数量的最大值，遇到1加1，遇到0置为cur+1（抢救一手
        int max = 1;

        for (int i = 0; i < 32; i++) {
            if ((num & (1 << i)) != 0) {//这里我们可以想象成有个指针从右至左来遍历判断，若为1计数器加1，
                cur += 1;
                insert += 1;

            } else {
                insert = cur + 1;
                cur = 0;
            }

            max = Math.max(max, insert);

        }
        return max;

    }

    public int reverseBits2(int num) {
        int cur = 0;
        int insert = 0;
        int max = 1;


        for (int i = 0; i < 32; i++) {
            if ((num & 1) != 0) {
                cur++;
                insert++;
            } else {
                insert = cur + 1;
                cur = 0;
            }
            num = num >>> 1;
            max = Math.max(max, insert);

        }

        return max;
    }


    //面试题05.06 整数转换
    public int convertInteger(int A, int B) {
        if (A == B) {
            return 0;
        }

        int count = 0;

        for (int i = 0; i < 32; i++) {
            if ((A & (1 << i)) == (B & (1 << i))) {
                continue;
            }

            count++;
        }


        return count;
    }

    //面试题05.07 配对交换
    /*
    0xaaaaaaaa = 10101010101010101010101010101010 (偶数位为1，奇数位为0）
    0x55555555 = 1010101010101010101010101010101 (偶数位为0，奇数位为1）
     */
    public int exchangeBits(int num) {
        int res = 0;

        int odd = num & 0x55555555;//拿到奇数位的个数

        int even = num & 0xaaaaaaaa;

        odd = odd << 1;
        even = even >>> 1;
        return odd | even;
    }


    public static void main(String[] args) {
        t20211023 t20211023 = new t20211023();

     /*   Scanner scanner = new Scanner(System.in);
        System.out.println("请输入你求和的次数");
        int input = scanner.nextInt();
        System.out.println(t20211023.sum(input));*/

        int N = 1024;//100 0000 0000
        int M = 19;//1 0011
        //100 1100

        /*
            i:2 j:6
         */
        System.out.println(16 & 0x55555555);

    }


}
